package leetcode.dynamic;

/*

给定一个由 0 和 1 组成的矩阵 mat ，请输出一个大小相同的矩阵，其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。

两个相邻元素间的距离为 1 。

 

示例 1：



输入：mat = [[0,0,0],[0,1,0],[0,0,0]]
输出：[[0,0,0],[0,1,0],[0,0,0]]
示例 2：



输入：mat = [[0,0,0],[0,1,0],[1,1,1]]
输出：[[0,0,0],[0,1,0],[1,2,1]]
 

提示：

m == mat.length
n == mat[i].length
1 <= m, n <= 104
1 <= m * n <= 104
mat[i][j] is either 0 or 1.
mat 中至少有一个 0 

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/01-matrix
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法1：
    从s[i][j] = 0位置bfs

解法二：
    1. 从s[i][j] 的位置计算四个方向上是s[m][n] = 1的距离
    2. 计算没有遍历到的位置(i, j)

 */

import java.util.Stack;

public class LeetCode541_UpdateMatrix {

    public int[][] updateMatrix(int[][] mat) {

        int[][] s = new int[mat.length + 2][mat[0].length + 2];
        int[][] visited = new int[mat.length + 2][mat[0].length + 2];
        Stack<int[]> zeroPosition = new Stack<>();

        for (int i = 0; i < s.length; i++){
            for (int j = 0; j < s[0].length; j++){

                if (i == 0 || j == 0 || i == s.length - 1 || j == s[0].length - 1){
                    s[i][j] = Integer.MAX_VALUE;
                    continue;
                }

                if (mat[i - 1][j - 1] == 0){
                    s[i][j] = 0;
                    zeroPosition.add(new int[]{i, j});
                }else {
                    s[i][j] = Integer.MAX_VALUE;
                }

            }
        }

        for (int[] arr : zeroPosition){
            int x = arr[0];
            int y = arr[1];

            visited[x][y] = 1;

            for (int i = y - 1; i >= 1; i--){
                if (s[x][i] != 0){
                    s[x][i] = Math.min(Math.min(s[x][i - 1], s[x][i + 1]), Math.min(s[x - 1][i], s[x + 1][i])) + 1;
                }
                visited[x][i] = 1;
            }

            for (int i = y + 1; i <= s[0].length - 2; i++){
                if (s[x][i] != 0){
                    s[x][i] = Math.min(Math.min(s[x][i - 1], s[x][i + 1]), Math.min(s[x - 1][i], s[x + 1][i])) + 1;
                }
                visited[x][i] = 1;
            }

            for (int i = x - 1; i >= 1; i--){
                if (s[i][y] != 0){
                    s[i][y] = Math.min(Math.min(s[i - 1][y], s[i + 1][y]), Math.min(s[i][y - 1], s[i][y + 1])) + 1;
                }
                visited[i][y] = 1;
            }

            for (int i = x + 1; i <= s.length - 2; i++){
                if (s[i][y] != 0){
                    s[i][y] = Math.min(Math.min(s[i][y - 1], s[i][y + 1]), Math.min(s[i - 1][y], s[i + 1][y])) + 1;
                }
                visited[i][y] = 1;
            }

        }

        for (int i = 1; i < s.length - 1; i++){
            for (int j = 1; j < s[0].length - 1; j++){
                if (visited[i][j] == 0){
                    s[i][j] = Math.min(Math.min(s[i][j - 1], s[i][j + 1]), Math.min(s[i - 1][j], s[i + 1][j])) + 1;
                }
            }
        }

        for (int i = 1; i < s.length - 1; i++){
            for (int j = 1; j < s[0].length - 1; j++){
                mat[i - 1][j - 1] = s[i][j];
            }
        }


        return mat;
    }

    public static void main(String[] args) {
//        int[][] mat = {{0,0,0},{0,1,0},{0,0,0}};
//        int[][] mat = {{0,0,0},{0,1,0},{1,1,1}};
        int[][] mat = {{1,1,1},{1,1,1},{1,1,1},{0,0,0}};
        //int[][] mat = {{0,0,0,0,1}};
        int[][] result = new LeetCode541_UpdateMatrix().updateMatrix(mat);

        System.out.println("result = " + result);
    }

}
